package com.leetcode;

/**
 * 给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。
 * 如果不存在 公共子序列 ，返回 0
 * 。例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。
 *
 * 两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。
 * 示例 1：
 * 输入：text1 = "abcde", text2 = "ace"
 *
 * 输出：3
 *
 * 解释：最长公共子序列是 "ace" ，它的长度为 3 。
 *
 * 作者：宫水三叶的刷题日记
 * 链接：https://juejin.cn/post/7113739259097382948
 * 来源：稀土掘金
 * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
 * @author wu
 * @create 2022-07-01-11:33
 */
public class LongestCommonSubsequence {

    public static void main(String[] args) {
        String a = "aefm";
        String b = "afoecemmf";
        int i = longestCommonSubsequence(a, b);
        System.out.println(i);
    }
    public static int longestCommonSubsequence(String s1, String s2) {
        int n = s1.length(), m = s2.length();
        s1 = " " + s1;
        s2 = " " + s2;
        char[] cs1 = s1.toCharArray(), cs2 = s2.toCharArray();
        int[][] f = new int[n + 1][m + 1];

        // 因为有了追加的空格，我们有了显然的初始化值（以下两种初始化方式均可）
        // for (int i = 0; i <= n; i++) Arrays.fill(f[i], 1);
        for (int i = 0; i <= n; i++) {
            f[i][0] = 1;
        }
        for (int j = 0; j <= m; j++) {
            f[0][j] = 1;
        }

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (cs1[i] == cs2[j]) {
                    f[i][j] = f[i - 1][j - 1] + 1;
                } else {
                    f[i][j] = Math.max(f[i - 1][j], f[i][j - 1]);
                }
            }
        }
        // 减去最开始追加的空格
        return f[n][m] - 1;
    }
    /**
     * 1
     * 2
     * 3
     */
}
